#include "tree.h"
#include <iostream>
using namespace std;

#define REDUCE(SYMBOL, CODE) \
    {this->reduce(); \
    this->i++; \
    this->allToken.push_back(token(SYMBOL,CODE)); \
    return true;}

class buffer
{
private:
    static bool isNum(char c)
    {
        return c>='0' && c<='9';
    }

    static bool isNum(string s)
    {
        for(auto i : s)
        {
            if(!buffer::isNum(i))
                return false;
        }
        return true;
    }

    static bool isLetter(char c)
    {
        return (c>='a' && c<='z') || (c>='A' && c<='Z');
    }

    static bool isLetter(string s)
    {
        if(buffer::isLetter(s[0]))
        {
            for(int i=1;i<s.size();i++)
            {
                if(!buffer::isLetter(s[i]) && !buffer::isNum(s[i]))
                    return false;
            }
            return true;
        }
        else
            return false;
    }

    bool isKeyword(vector<token> &allToken)
    {
        if(this->buffer=="begin")
        {
            allToken.push_back(token("begin",1));
            this->clear();
            return true;
        }
        else if(this->buffer=="if")
        {
            allToken.push_back(token("if",2));
            this->clear();
            return true;
        }
        else if(this->buffer=="then")
        {
            allToken.push_back(token("then",3));
            this->clear();
            return true;
        }
        else if(this->buffer=="while")
        {
            allToken.push_back(token("while",4));
            this->clear();
            return true;
        }
        else if(this->buffer=="do")
        {
            allToken.push_back(token("do",5));
            this->buffer="";
            return true;
        }
        else if(this->buffer=="end")
        {
            allToken.push_back(token("end",6));
            this->clear();
            return true;
        }
        return false;
    }

public:
    string buffer;

    void add(char c) { this->buffer+=string(1,c); }
    void clear() { this->buffer=""; }
    void reduce(vector<token> &allToken)
    {
        if(this->buffer=="")
            return;
        else if(this->isKeyword(allToken))
            return;
        else
        {
            //判断数字
            if(buffer::isNum(this->buffer))
            {
                allToken.push_back(token(this->buffer,11));
                this->clear();
                return;
            }
            //判断letter
            else if(buffer::isLetter(this->buffer))
            {
                allToken.push_back(token(this->buffer,10));
                this->clear();
                return;
            }
            else
                throw string("reduce error: "+this->buffer);
        }
    }
};


class lexer
{
private:
    string program;
    unsigned int i=0;
    buffer b;
    void reduce() { this->b.reduce(allToken); }

    static bool test2Str(string s1, string s2, unsigned int &i)
    {
        for(int j=0;j<s2.size();j++)
        {
            if(s1[j+i]!=s2[j])
                return false;
        }
        //暂时不直接pushback
        i=i+s2.size();
        return true;
    }

    bool isOp()
    {
        if(this->program[i]=='+')
            REDUCE("+",13)
        else if(this->program[i]=='-')
            REDUCE("-",14)
        else if(this->program[i]=='*')
            REDUCE("*",15)
        else if(this->program[i]=='/')
            REDUCE("/",16)
        else if(this->program[i]=='>')
            REDUCE(">",20)
        else if(this->program[i]=='<')
            REDUCE("<",23)
        return false;
    }

    bool isTerminator()
    {
        if(this->program[i]==' ')
        {
            this->reduce();
            this->i++;
            return true;
        }
        else if(this->program[i]==';')
            REDUCE(";",26)
        else if(lexer::test2Str(this->program,":=",this->i))
        {
            this->reduce();
            this->allToken.push_back(token(":=",18));
            return true;
        }
        else if(this->i==program.size())
        {
            this->reduce();
            this->i++;
            return true;
        }
        else
            return this->isOp();
    }

public:
    vector<token> allToken;
    lexer(string program) : program(program) {}

    void run()
    {
        while(this->i<=this->program.size())
        {
            if(!this->isTerminator()) //这里面会消耗字符
            {
                this->b.add(this->program[i]);
                this->i++;
            }
        }
    }
};

class parser
{
private:
    unsigned int i=0;

    static bool isOp(token t)
    {
        return (t.second>=13 && t.second<=16) || (t.second>=20 && t.second<=25);
    }

    static bool isOpable(token t)
    {
        return t.second==10 || t.second==11;
    }

    node* _exp()
    {
        if(this->isOpable(allToken[i]))
        {
            auto opable1=allToken[i];
            this->i++;

            node* n_opable1=new node(opable1); //只有操作数的节点

            //后面可以接操作符，也可以不接
            //表达式的结束标志，但这个token不消耗
            while(allToken[i].first!=";" && allToken[i].first!="then")
            {
                if(isOp(allToken[i])) //接操作符，递归
                {
                    auto op=allToken[i];
                    this->i++;

                    node* n=new node(op);
                    n->add(n_opable1);

                    auto subExpRet=this->_exp();
                    if(subExpRet!=nullptr)
                    {
                        n->add(subExpRet);
                        return n;
                    }
                    else //子表达式解析失败
                        return nullptr;
                }
                else //后面既不是操作符，也不满足表达式终止条件
                    return nullptr;
            }
            return n_opable1;
        }
        return nullptr;
    }

    node* _statement()
    {
        //赋值语句
        if(allToken[i].second==10) //第一个是letter
        {
            auto opable1=allToken[i];
            this->i++;
            if(allToken[i].first==":=") //然后是赋值号
            {
                auto op=allToken[i];
                this->i++;
                //然后是表达式
                auto expRet=this->_exp();
                if(expRet!=nullptr)
                {
                    if(allToken[i].first==";")
                    {
                        this->i++;
                        node* n=new node(op);
                        n->add(opable1);
                        n->add(expRet);
                        return n;
                    }
                }
            }
        }
        //if语句
        else if(allToken[i].first=="if")
        {
            auto op=allToken[i];
            this->i++;
            //if的条件是一个exp
            auto expRet=this->_exp();
            if(expRet!=nullptr)
            {
                if(allToken[i].first=="then")
                {
                    this->i++;
                    //由于例程里没有endif（语句块结束符），只能认为这种子语句块只能容纳一个语句
                    auto statRet=this->_statement();
                    if(statRet!=nullptr)
                    {
                        node* n=new node(op);
                        n->add(expRet);
                        n->add(statRet);
                        return n;
                    }
                }
            }
        }
        return nullptr;
    }

    node* _statementBlock()
    {
        node* n=new node(token("_statementBlock",29));
        while(allToken[i].first!="end")
        {
            auto statRet=this->_statement();
            if(statRet!=nullptr)
            {
                n->add(statRet);
            }
            else
                return nullptr;

            if(i >= allToken.size())
                return nullptr;
        }
        return n;
    }

    node* _program()
    {
        if(allToken[i].first=="begin")
        {
            this->i++;
            auto sbRet=this->_statementBlock();
            if(sbRet!=nullptr)
            {
                if(allToken[i].first=="end")
                {
                    this->i++;
                    return sbRet;
                }
            }
        }
        return nullptr;
    }

public:
    vector<token> allToken;
    parser(vector<token> allToken) : allToken(allToken){}
    node* run() { return this->_program(); }
};

int main()
{
    string program="begin x111:=9;if x>0 then x:=2*x+1/3;end";
    lexer l(program);
    try
    {
        l.run();
    }
    catch (string s)
    {
        cout<<s<<endl;
    }

    for(auto i : l.allToken)
        cout<<i.first<<" "<<i.second<<endl;

    cout<<endl<<"parser:"<<endl;

    parser p(l.allToken);
    node* tree=p.run();
    if(tree==nullptr)
        cout<<"parser Error!"<<endl;
    else
        tree->output();
}
